#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <cstring>

using namespace std;

// 飞行路线（自己手撸的堆）
// Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司
// 该航空公司一共在n个城市设有业务，设这些城市分别标记为0 ~ n−1
// 一共有m种航线，每种航线连接两个城市，并且航线有一定的价格
// Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机
// 航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机
// 那么 Alice 和 Bob 这次出行最少花费多少
// 测试链接 : https://www.luogu.com.cn/problem/P4568
// 提交以下所有代码，可以直接通过

const int MAXN = 10001; // 城市的最大数量
const int MAXM = 100001; // 有向边的最大数量
const int MAXK = 11; // 免费乘坐的最大次数

// 链式前向星需要的
int head[MAXN];
int next[MAXM];
int to[MAXM];
int weight[MAXM];
int cnt;

// Dijkstra 需要的
int dist[MAXN][MAXK];
bool visited[MAXN][MAXK];

// 自己写的普通堆，静态结构，推荐
// 注意是自己写的普通堆，不是反向索引堆
// 因为(点编号，使用免费路线的次数)，两个参数的组合才是图中的点
// 两个参数的组合对应一个点(一个堆的下标)，所以反向索引堆不好写
// 其实也能实现，二维点变成一维下标即可
// 但是会造成很多困惑，索性算了，就手写普通堆吧
// 0 : 沿途的花费
// 1 : 到达的城市编号
// 2 : 已经使用的免单次数
int heap[MAXM * MAXK][3];
int heapSize;
int n, m, k, s, t;
int cost, u, use; // 全局变量，用来接收 pop 的结果

void build(int n)
{
    cnt = 1;
    heapSize = 0;
    memset(head, 0, sizeof(head));
    memset(dist, 0x3f, sizeof(dist));
    memset(visited, 0, sizeof(visited));
}

void addEdge(int u, int v, int w)
{
    ::next[cnt] = head[u];
    to[cnt] = v;
    weight[cnt] = w;
    head[u] = cnt++;
}

void swap(int i, int j)
{
    // int tmp[3];
    // memcpy(tmp, heap[i], sizeof(tmp));
    // memcpy(heap[i], heap[j], sizeof(tmp));
    // memcpy(heap[j], tmp, sizeof(tmp));
    std::swap(heap[i], heap[j]);
}

// 注意：这里使用的是局部变量 cost u use
// 0 cost : 沿途的花费
// 1 u : 到达的城市编号
// 2 use : 已经使用的免单次数
// 向上调整算法
void push(int cost, int u, int use)
{
    heap[heapSize][0] = cost; 
    heap[heapSize][1] = u;
    heap[heapSize][2] = use;
    int i = heapSize++;
    while(heap[i][0] < heap[(i - 1) / 2][0])
    {
        ::swap(i, (i - 1) / 2);
        i = (i - 1) / 2;
    }
}

// 向下调整算法
void heapify(int i)
{
    int l = 2 * i + 1;
    while(l < heapSize)
    {
        int best = l + 1 < heapSize && heap[l + 1][0] < heap[l][0] ? l + 1 : l;
        best = heap[best][0] < heap[i][0] ? best : i;
        if(best == i) break;
        ::swap(best, i);
        i = best;
        l = 2 * i + 1;
    }
}

void pop()
{
    cost = heap[0][0];
    u = heap[0][1];
    use = heap[0][2];
    ::swap(0, --heapSize); 
    heapify(0); // 向下调整算法
}

bool isEmpty()
{
    return heapSize == 0;
}

int dijkstra()
{
    dist[s][0] = 0;
    // 0 : 沿途的花费
    // 1 : 到达的城市编号
    // 2 : 已经使用的免单次数
    push(0, s, 0);
    while(!isEmpty())
    {
        pop();
        if(visited[u][use]) continue;

        visited[u][use] = true;
        // 常见剪枝
        // 发现终点直接返回
        // 不用等都结束
        if(u == t) return cost;
        // 链式前向星遍历
        for(int ei = head[u]; ei > 0; ei = ::next[ei])
        {
            int v = to[ei], w = weight[ei];
            // 使用免费次数：加 + 0 表示使用了免费次数
            if(use < k && dist[v][use + 1] > dist[u][use] + 0)
            {
                dist[v][use + 1] = dist[u][use] + 0;
                push(dist[v][use + 1], v, use + 1);
            }
            // 不使用免费次数
            if(dist[v][use] > dist[u][use] + w)
            {
                dist[v][use] = dist[u][use] + w;
                push(dist[v][use], v, use);
            }
        }
    }

    return -1;
}

int main()
{
    cin >> n >> m >> k >> s >> t;
    build(n);
    for(int i = 0; i < m; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }    
    cout << dijkstra() << endl;

    return 0;
}